package com.dynamicPlanning;

/**
 * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
 */
public class GetLongestPalindrome {
    public static void main(String[] args) {
        System.out.println(getLongestPalindrome3("abccba"));

    }

    /**
     * 中心扩散法
     *图片中我们是以每一个字符为中心，往两边扩散，来求最长的回文子串。
     * 但忽略了一个问题，回文串的长度不一定都是奇数，也可能是偶数，比如字符串"abba"。
     * 我们来思考这样一个问题，如果是单个字符，我们可以认为他是回文子串，如果是多个字符，并且他们都是相同的，那么他们也是回文串。
     * 所以对于上面的问题，我们以当前字符为中心往两边扩散的时候，先要判断和他挨着的有没有相同的字符，如果有，则直接跳过，来看下代码
     */
    public static int getLongestPalindrome1(String A) {
        //如果字符串的长度小于2直接返回字符串的长度
        int n = A.length();
        if(n < 2){
            return n;
        }
        //maxLen表示最长回文串的长度
        int maxLen = 0;
        for (int i = 0; i < n;) {
            int left = i;
            int right = i;
            //如果剩余子串的长度小于目前查找的最长回文子串的长度一般，直接终止循环
            //应为即使后面有回文串也不是最长的
            if(n - i < maxLen/2){
                break;
            }
            while(n-1 > right && A.charAt(right+1) == A.charAt(right)){
                ++right;//防止出现相同的字符串
            }
            //向两边判断，找出回文串的长度
            while (n-1 > right && left > 0 && A.charAt(right+1) == A.charAt(left-1)){
                ++right;
                --left;
            }
            maxLen = Math.max(right - left + 1,maxLen);
            //下次在判断的时候从重复的下一个字符开始判断
            i = right + 1;
        }
        return maxLen;
    }

    /**
     * 暴力求解发
     * 要截取字符串的所有子串，然后再判断这些子串中哪些是回文的，最后返回回文子串中最长的即可。
     * 这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串的长度，最后再截取
     */
    public static int getLongestPalindrome2(String A) {
        int n = A.length();
        //边界条件判断
        if (n < 2){
            return A.length();
        }
        int maxLen = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i; j < n; j++) {
                //截取所有子串，然后在逐个判断是否是回文的
                if (j-i<maxLen/2){
                    continue;
                }
                if (isPalindrome(A, i, j)) {
                    if (maxLen < j - i + 1) {
                        maxLen = j - i + 1;
                    }
                }
            }
        }
        return maxLen;
    }
    //判断是否是回文串
    private static boolean isPalindrome(String s,int start,int end){
        while (start < end){
            if(s.charAt(start++) != s.charAt(end--)){
                return false;
            }
        }
        return true;
    }

    /**
     * 动态规划法
     */
    public static int getLongestPalindrome3(String A) {
        int n = A.length();
        //边界条件判断
        if (n < 2)
            return A.length();
        //start表示最长回文串开始的位置，
        //maxLen表示最长回文串的长度
        int maxLen = 1;
        boolean[][] dp = new boolean[n][n];
        for (int right = 1; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                //如果两种字符不相同，肯定不能构成回文子串
                if (A.charAt(left) != A.charAt(right)) {
                    continue;
                }
                //下面是s.charAt(left)和s.charAt(right)两个
                //字符相同情况下的判断
                //如果只有一个字符，肯定是回文子串
                if (right == left) {
                    dp[left][right] = true;
                } else if (right - left <= 2) {
                    //类似于"aa"和"aba"，也是回文子串
                    dp[left][right] = true;
                } else {
                    //类似于"a******a"，要判断他是否是回文子串，只需要
                    //判断"******"是否是回文子串即可
                    dp[left][right] = dp[left + 1][right - 1];
                }
                //如果字符串从left到right是回文子串，只需要保存最长的即可
                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                }
            }
        }
        //最长的回文子串
        return maxLen;
    }
}
